package first.codeTop.byteDance;

/**
 * @ClassName Leetcode53
 * @description:
 * @author: 荣燊
 * @create: 2021-07-26 10:19
 **/
public class Leetcode53 {
    // 最大子序列和,注意是连续的子数组
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

    // dp[i]表示数组中第i位结尾的连续子数组的和
    public static int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int maxSum = dp[0];
        for (int i=1; i<nums.length; i++) {
            if (dp[i-1] > 0) {
                dp[i] = dp[i-1] + nums[i];
            } else {
                dp[i] = nums[i];
            }
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}
